package NO2908;

public class No2908 {
    public static void main(String[] args) {
        int[] nums = new int[]{5, 4, 8, 7, 10, 2};
        System.out.println(new No2908().minimumSum(nums));
    }

    public int minimumSum(int[] nums) {
        /**
         * 关键点: 左边一定存在比中间山峰小的值
         *        右边一定存在比中间山峰小的值
         * 前后缀分解
         * 从左至右扫描 保留最小
         * 从右至左扫描 保留最小
         * 中间  最小的山顶
         * 以上三个数 既是 元素和最小的山形三元组
         */

        int size = nums.length;
        int leftMin = 50, rightMin = nums[size - 1];
        int result = 150;
        boolean flag = false;
        int left[] = new int[size];
        for (int i = 0; i < size; i++) {
            left[i] = leftMin = Math.min(nums[i], leftMin);
        }

        // 最左边 i = 0 ， 最右边 i = size-1 不计算
        for (int i = size - 2; i > 0; i--) {
            // nums[i] 大于 前缀最小  大于后缀最小
            rightMin = Math.min(nums[i + 1], rightMin);
            if (nums[i] > left[i - 1] && nums[i] > rightMin) {
                flag = true;
                result = Math.min((left[i - 1] + nums[i] + rightMin), result);
            }
        }
        return flag ? result : -1;

    }
}
